package com.code.test.first.link;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.md
 * <p>
 * 题意：删除链表中等于给定值 val 的所有节点。
 * <p>
 * 示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
 * <p>
 * 示例 2： 输入：head = [], val = 1 输出：[]
 * <p>
 * 示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]
 */
public class Code203 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(6);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(4);
        ListNode n6 = new ListNode(5);
        ListNode n7 = new ListNode(7);

        head.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);


    }

    public static ListNode removeElements(ListNode head, int target) {
        if (head == null) return null;

        ListNode dummy = new ListNode(-1);
        dummy.setNext(head);

        ListNode pre = dummy;
        ListNode cur = head;
        /**
         * 不断移动pre和cur，直到cur为空
         */
        while (cur != null) {
            if (cur.getVal() == target) {
                pre.setNext(cur.getNext());
            } else {
                pre = cur;
            }

            cur = cur.getNext();
        }
        return dummy.getNext();
    }

    public static ListNode removeElements2(ListNode head, int target) {
        while (head != null && head.getVal() == target) {
            head = head.getNext();
        }
        if (head == null) {
            return null;
        }

        /**
         * 此时head没有等于target的值
         */
        ListNode pre = head;
        ListNode cur = head.getNext();
        while (cur != null) {
            if (cur.getVal() == target) {
                //等于target，则删除，把下一个赋值给pre
                pre.setNext(cur.getNext());
            } else {
                //没找到，则pre往后移
                pre = cur;
            }
            //cur往后移
            cur = cur.getNext();
        }

        return head;
    }
}
